//
// Created by 高森森 on 2022/2/11.
//

#ifndef LEETCODE_SOLUTION35_H
#define LEETCODE_SOLUTION35_H

#include <iostream>
#include<vector>
using namespace std;

class Solution35 {
public:
    int ans=0;
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        vector<vector<pair<int,int>>>graph(values.size());
        for(auto edge:edges){
            graph[edge[0]].emplace_back(edge[1],edge[2]);
            graph[edge[1]].emplace_back(edge[0],edge[2]);
        }
        vector<bool>visited(values.size());
        visited[0]=true;
        dfs(0,0,maxTime,values[0],values,visited,graph);
        return ans;
    }
    void dfs(int u,int time,int maxTime,int value,vector<int>&values,vector<bool>&visited,vector<vector<pair<int,int>>>&graph){
        if(time>maxTime)
            return;
        if(u==0)
            ans=max(ans,value);
        for(auto &node:graph[u]){
            int v=node.first;
            int w=node.second;
            if(!visited[v]){
                visited[v]=1;
                dfs(v,time+w,maxTime,value+values[v],values,visited,graph);
                visited[v]=0;
            }else{
                dfs(v,time+w,maxTime,value,values,visited,graph);
            }
        }

    }
};


#endif //LEETCODE_SOLUTION35_H
